The various links of a computer network are paths between network nodes that communicate streams of data. In an Internet Protocol (IP) based computer network, data routing protocols such as Open Shortest Path First (OSPF), Intermediate System-Intermediate System (IS-IS), and Routing Information Protocol (RIP) are used to determine the path that data packets travel through the network. As a specific example, OSPF is a link-state protocol in the IP suite that enables routers to exchange information regarding topological changes within the network, as the link state database is modified. With this information, each router builds a shortest-path tree with itself as the tree root to identify the shortest path from itself to each destination and to build its routing table.
A router in a label switching network may sometimes explicitly route a particular data packet to another intermediate router that is not the ultimate destination of the packet, even though the two routers are not consecutive on the hop-by-hop path for that packet. For example, the affected data packet may be encapsulated inside a network layer packet whose destination is the intermediate router. This process establishes a “tunnel” between the two routers, and any data packet so handled is referred to as a “tunneled packet.” A hop-by-hop tunnel follows the hop-by-hop path between the two routers. A tunneled packet that follows other than the hop-by-hop path is said to use an explicitly routed tunnel.
Occasionally, a link between two network routers may fail. When a link fails, the routing protocols are used to advertise the failure throughout the network. Most routers can detect a local link failure relatively quickly, but it takes the network as a whole a much longer time to converge. This convergence time is typically on the order of 10-60 seconds depending on the routing protocol and the size of the network. Eventually, all of the involved routers learn of the link failure and compute new routes for data packets to affected destinations. Once all the routers converge on a new set of routes, data packet forwarding proceeds normally.
While the network is converging after a link fails, transient loops can occur which consume valuable network bandwidth. A loop occurs when two or more intermediate routers in a given network path fail to update their internal representations of the network topology at the same time, and end up repeatedly passing data traffic between themselves rather than on to the correct destination. Loop prevention algorithms have been proposed to eliminate such transient loops. When using loop prevention algorithms, existing routes are maintained until the network has converged and the new routes have been proven to be loop-free. Loop prevention algorithms have the advantage that data packets flowing on unaffected routes are not disrupted while transient loops are eliminated. One drawback of loop prevention algorithms, however, is that data packets directed out of a failed link get lost, or “black holed,” during the convergence. Moreover, since loop prevention algorithms also extend the convergence time somewhat while new routes are being verified to be loop-free, additional data may be lost on the failed link.